package DoblePointer;//给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
//
// 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。 
//
// 
//
// 示例 1: 
//
// 
//输入: num1 = "2", num2 = "3"
//输出: "6" 
//
// 示例 2: 
//
// 
//输入: num1 = "123", num2 = "456"
//输出: "56088" 
//
// 
//
// 提示： 
//
// 
// 1 <= num1.length, num2.length <= 200 
// num1 和 num2 只能由数字组成。 
// num1 和 num2 都不包含任何前导零，除了数字0本身。 
// 
// Related Topics 数学 字符串 模拟 👍 901 👎 0


import java.util.ArrayList;

//leetcode submit region begin(Prohibit modification and deletion)
class multiply {
    public static String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        //让num1表示长字符串，num2表示短字符串
        if(len1 < len2){
            String temp = num1;
            num1 = num2;
            num2 = temp;

            int te = len1;
            len1 = len2;
            len2 = te;
        }

        ArrayList<String> strings = new ArrayList<>();
        //模拟乘法运算，一次取nums2的一位与另一个进行乘法。
        int index = len2-1; //初始从末尾开始
        while(index >= 0){
            char c = num2.charAt(index); //获取乘数
            String r = stringMulti(num1, c); //当前乘数与num1相乘的结果
            //因为有进位，判断是否需要补0
            for(int i=0;i< len2-1 - index;i++){
                r += "0";
            }
            strings.add(r);
            index--;
        }
        String res = "";
        for (int i = 0; i < strings.size(); i++) {
            res = stringAdd(res, strings.get(i));
        }
        return res;


    }

    //nums1是长串，nums2是单字符
    public static String stringMulti(String nums1, char nums2){
        int len = nums1.length();
        int i = len-1;
        StringBuilder sb = new StringBuilder();
        int flag = 0;
        while(i>=0){
            int n1 = nums1.charAt(i)-'0';
            int n2 = nums2-'0';
            int multi = n1 * n2 + flag;
            sb.append(multi%10);
            flag = multi/10;
            i--;
        }
        if(flag>0){
            sb.append(flag);
        }
        return sb.reverse().toString();
    }



    //两个字符串相加
    public static String stringAdd(String num1, String num2){

        int flag = 0;
        int i = num1.length()-1;
        int j = num2.length()-1;
        StringBuilder sb = new StringBuilder();
        while(i>=0 || j>=0){
            int n1 = i>=0 ? num1.charAt(i)-'0' : 0 ;
            int n2 = j>=0 ? num2.charAt(j)-'0' : 0 ;
            int sum = n1 + n2 + flag;
            flag = sum/10;
            sum = sum%10;
            sb.append(sum);
            i--;
            j--;
        }
        if(flag==1){
            sb.append("1");
        }
        return sb.reverse().toString();

    }

    public static void main(String[] args) {
        System.out.println(multiply("123","456"));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
